"""
235. 二叉搜索树的最近公共祖先

     * 思路：首先是通过遍历二叉树的方式，其次，公共节点满足：value1.val <= root.val <= value2.val，
     *     且如果 value1.val > root.val，则去左子树找，如果 root.val > value2.val，则去右子树查
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        min_val = min(p.val, q.val)
        max_val = max(p.val, q.val)
        return self.find(root, min_val, max_val)

    '''遍历二叉树'''
    def find(self, root: Optional[TreeNode], min_val: int, max_val: int):
        if not root:
            return
        # 前序位置
        if max_val < root.val:
            return self.find(root.left, min_val, max_val)
        # 中序位置
        if min_val > root.val:
            return self.find(root.right, min_val, max_val)
        # 后序位置
        return root

